//<p>给定一个仅包含数字&nbsp;<code>2-9</code>&nbsp;的字符串，返回所有它能表示的字母组合。答案可以按 <strong>任意顺序</strong> 返回。</p>
//
//<p>给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。</p>
//
//<p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png" style="width: 200px;" /></p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>digits = "23"
//<strong>输出：</strong>["ad","ae","af","bd","be","bf","cd","ce","cf"]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>digits = ""
//<strong>输出：</strong>[]
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>digits = "2"
//<strong>输出：</strong>["a","b","c"]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>0 &lt;= digits.length &lt;= 4</code></li>
//	<li><code>digits[i]</code> 是范围 <code>['2', '9']</code> 的一个数字。</li>
//</ul>
//<div><div>Related Topics</div><div><li>哈希表</li><li>字符串</li><li>回溯</li></div></div><br><div><li>👍 1887</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import cn.hutool.json.JSONUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 电话号码的字母组合
 * @author DY Rising
 * @date 2022-05-09 20:23:19
 */
public class P17_LetterCombinationsOfAPhoneNumber{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P17_LetterCombinationsOfAPhoneNumber().new Solution();
        String digits = "23";
        System.out.println(JSONUtil.toJsonStr(solution.letterCombinations(digits)));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, List<Character>> orign = new HashMap<>();
        orign.put('2', Arrays.asList('a', 'b', 'c'));
        orign.put('3', Arrays.asList('d', 'e', 'f'));
        orign.put('4', Arrays.asList('g', 'h', 'i'));
        orign.put('5', Arrays.asList('j', 'k', 'l'));
        orign.put('6', Arrays.asList('m', 'n', 'o'));
        orign.put('7', Arrays.asList('p', 'q', 'r', 's'));
        orign.put('8', Arrays.asList('t', 'u', 'v'));
        orign.put('9', Arrays.asList('w', 'x', 'y', 'z'));
        char[] chars = digits.toCharArray();
        Map<Character, List<Character>> all = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            all.put(chars[i], orign.get(chars[i]));
        }
        List<String> rtns = new ArrayList<>();
        str(all, chars, chars.length, 0, rtns, "");
        return rtns;
    }

    public void str(Map<Character, List<Character>> all, char[] chars, int length, int deep, List<String> rtns, String str) {
        if (deep >= length) return;
        List<Character> characters = all.get(chars[deep]);
        int i = 0;
        while (i < characters.size()) {
            if (deep == length - 1) {
                rtns.add(str + characters.get(i));
            } else {
                str(all, chars, length, deep + 1, rtns, str + characters.get(i));
            }
            i++;
        }

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
